import java.util.ArrayList;
import java.util.List;

public class Solution {
    //面试题1：移动值为val的元素
    public int removeElement(int[] nums, int val) {
        int usesized = 0;
        //将不等于val的元素放到数组的usized中即可
        for(int i = 0;i < nums.length;i++){
            if(nums[i] != val){
                nums[usesized] = nums[i];
                usesized++;
            }
        }
        return usesized;
    }
    //2、删除有序数组中的重复项
    public int removeDuplicates(int[] nums) {
            int usesized = 1;
            for(int i = 1; i < nums.length;i++){
                if(nums[i] != nums[i-1]){
                    nums[usesized] = nums[i];
                    usesized++;
                }
            }
            return usesized;
        }
    //3、合并两个有序数组
        public void merge(int[] nums1, int m, int[] nums2, int n) {
            int i = m - 1;
            int j = n - 1;
            int k = m + n - 1;
            while(i >= 0 && j >= 0){
                if(nums1[i] > nums2[j]){
                    nums1[k] = nums1[i];
                    i--;
                    k--;
                }else{
                    nums1[k] = nums2[j];
                    j--;
                    k--;
                }
            }
            while(i >= 0){
                nums1[k] = nums1[i];
                i--;
                k--;
            }
            while(j >= 0){
                nums1[k] = nums2[j];
                j--;
                k--;
            }
    }
        public static List<List<Integer>> generate(int numRows) {
            List<List<Integer>> ret = new ArrayList<>();
            List<Integer> row = new ArrayList<>();
            row.add(1);
            ret.add(row);
            //第一行已经处理完
            //下面代码从第2行开始
            for (int i = 1; i < numRows; i++) {
                List<Integer> curRow = new ArrayList<>();
                curRow.add(1);//当前行的第一个元素
                //这里处理中间列
                //上一行
                List<Integer> prevRow = ret.get(i-1);
                for (int j = 1; j < i; j++) {
                    int x = prevRow.get(j) + prevRow.get(j-1);
                    curRow.add(x);
                }
                curRow.add(1);//当前行的最后一个元素
                ret.add(curRow);
            }
            return ret;
        }
}
